package practise.alogrithm.hundredInterviewQuestions.secondTime;

/**
 * todo have defect
 */
public class LargestCommonSubsequence {
    /**
     * we use dynamic programming here
     * d(start,length) = d(start,length-1)+1 | endIndex in A,B>(endIndex-1) in A,B
     */
    public void find(String arg1, String arg2){
        int[] maxLength=new int[arg1.length()];
        int max =0,maxStartIndex=0;
        int[][] matrix = new int[arg1.length()][arg1.length()];
        for(int index=0; index<arg1.length();index++){
            //init the value at length 1
            matrix[index][1]=-1;
        }
        for(int length=1; length<=arg1.length();length++){
            for(int index =length-1; index<arg1.length();index++){
                for(int index2=0; index2<arg2.length();index2++){
                    if(arg1.charAt(index)==arg2.charAt(index2)){
                        if(length==1) {//first time we found a char in arg2
                            if(matrix[index][length]<0){
                                // have not found any one
                                matrix[index][length] = index2;
                            }
                            else {
                                //already find one,try to find next
                            }
                            maxStartIndex=index-length+1;
                            maxLength[index-length+1] =1;
                            max = 1;
                        }
                        else if(matrix[index-length+1][maxLength[index-length+1]]>0 && matrix[index-length+1][maxLength[index-length+1]]<index2){
                            maxLength[index-length+1] ++;
                            matrix[index-length+1][maxLength[index-length+1]] = index2;
                            if(max<=maxLength[index-length+1]){
                                max=maxLength[index-length+1];
                                maxStartIndex=index-length+1;
                            }
                        }
                    }
                }
            }
        }

        System.out.println("MaxIndex:"+maxStartIndex+"MaxLength:"+maxLength[maxStartIndex]);
        for(int index=1;index<=maxLength[maxStartIndex];index++){
            System.out.print(arg2.charAt(matrix[maxStartIndex][index]));
        }
    }

    public static void main(String[] args){
        LargestCommonSubsequence largestCommonSubsequence = new LargestCommonSubsequence();
        largestCommonSubsequence.find("BDCAB","ABCBDAB");// BDCABA,ABCBDABA
    }
}
